/*
 * @lc app=leetcode.cn id=132 lang=cpp
 *
 * [132] 分割回文串 II
 */

// @lc code=start
class Solution {
public:
    int minCut(string s) {
        int size = s.size();
        vector<vector<int>> f(size,vector<int>(size,true));

        // 找到字符串中的分割序列
        for(int i = size - 1 ;i >= 0 ; i--)
        {
            for(int j = i + 1; j < size ; j++)
            {
                f[i][j] = (s[i] == s[j]) && f[i+1][j-1];
            }
        }


        //
        vector<int> times(size,INT_MAX);
        for(int i = 0;i< size;i++)
        {
            if(f[0][i])
            {
                times[i] = 0;
            }
            for(int j = 0; j < i ; j++)
            {
                if(f[j+1][i])
                {
                    times[i] = min(times[i],times[j] + 1);
                }
            }
        }
        return times[size-1];
    }
};
// @lc code=end

